In the rapidly evolving landscape of web services, efficient interaction and optimal selection among services with different quality parameters are essential. This paper addresses the complex challenge of selecting candidate services for abstract services within probabilistic graph structures. We propose a new hybrid method that combines node-based and path-based graph simplification techniques, allowing for the identification of new patterns, such as parallel and nested loops. We use NSGAII to improve scalability and accuracy in service selection. The proposed approach simplifies the composition graph while optimizing the selection process by considering important quality parameters such as execution cost, response time, and availability. Through systematic simplification and a robust fitness function, we ensure a definitive and accurate response to user queries. The results show significant improvements in the proposed approach compared to existing methods, making it a comprehensive solution for effectively composing web services in dynamic environments.